class Solution {
    public static void main(String[] args) {
        String  s= "aaa" ;
        System.out.println(countSubstrings(s));
    }
    public static int countSubstrings(String s) {
        int len = s.length() ;
        int[][] dp = new int[len][len] ;
        int sum = 0 ;
        char[] arr = s.toCharArray() ;
        for(int i=len-1 ; i >= 0 ; i --){
            for(int j=i ; j < len ; j ++){
                if(arr[i] == arr[j]){
                    dp[i][j] = i==j?1:(i+1==j?1:dp[i+1][j-1]);
                }
                sum += dp[i][j] ;
            }
        }

        return sum ;
    }
}